- Title
- On the structure of polytopes related to the Hamilton Cycle Problem
- Creator
- Mohammadian, Sogol
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2020
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- The Hamilton Cycle Problem (HCP) is one of the classical problems in combinatorics. The problem is to decide if a given graph G contains a cycle that visits each node exactly once. Cycles that pass through every node of a graph exactly once are called Hamilton cycles. If a graph contains at least one Hamilton cycle, then it is called Hamiltonian. Otherwise, it is non-Hamiltonian. It is known that the HCP is NP-complete, so it is unlikely that there is an exact algorithm which terminates in polynomial time and solves the problem in general. However, there are many very successful heuristics, and a lot of research has been done towards a theoretical understanding of the performance of these algorithms. In particular, there is an extensive literature on algorithms for finding Hamilton cycles in random graphs. Nevertheless, some questions in this area are still open (see, for example, [28]). In 1994, Filar and Krass [24] proposed a new approach to the HCP based on the theory of Markov Decision Processes (MDPs). Their approach initiated a new line of research studying various closely related polytopes constructed from an input graph G. In particular, two polytopes depending on a parameter β, 0 < β < 1, were introduced in [21]. We refer to these polytopes as Hβ(G) and WHβ(G). Their points correspond to discounted occupational measures induced by the MDP policies. There is a correspondence between the Hamilton cycles of a given graph G and specific extreme points of the polytopes mentioned above. As a consequence, these polytopes can be utilised as the basis for a sampling-based random walk algorithm to search for Hamilton cycles. The essential conditions for the efficiency of this approach are (i) existence of sufficiently many extreme points corresponding to Hamilton cycles, (ii) rapid mixing of the random walk, and (iii) polynomial run-time for a single step in the random walk. The third condition is always satisfied for the walk on the feasible bases as in this case the steps are, in fact, pivots in the simplex algorithm. In this thesis, we make the observation that if we assume two widely believed conjectures in complexity theory ( P ≠ NP and P = BPP) then the three necessary conditions cannot hold in full generality. However, this does not rule out that the approach works for particular classes of graphs. Interestingly, the algorithm from [30] for the random regular graph can be interpreted as a sampling-based search algorithm on the nodes of the polytope WH₁(G) which is obtained by setting β = 1 in the definition of WHβ(G). This gives rise to the following question, which motivates the research presented in this thesis: Does sampling extreme points (or feasible bases) of polytopes and solve any of the algorithmic questions for random graphs that are still open? In this thesis, we make some progress towards answering this question by establishing combinatorial results on the structure of these polytopes. Results on: We characterise the feasible bases of this polytope for a general input graph. Furthermore, we determine the expected numbers of different types of extreme points and feasible bases when the underlying graph is random. Our results indicate that the total number of feasible bases of the polytope grows exponentially faster than the number of Hamiltonian bases for an input random graph, and a similar result is true if we consider extreme points instead of feasible bases. As a consequence, sampling extreme points or feasible bases of this polytope cannot lead to an efficient sampling-based algorithm. We present some computational evidence that the behaviour of is more promising, which provides the motivation for a more in-depth study of this polytope. Results on: We present two general results about the structure of feasible bases for the polytope. First, we show that the set of feasible bases is independent of when the parameter is close to one. This ensures that we can study the combinatorics of the polytope without worrying about numerical issues caused by values of very close to 1. Second, we show that can be interpreted as a generalised network flow polytope. This connects the polytope to some classical combinatorial optimisation, and allows us to prove strong statements about the combinatorial structure of the feasible bases. For a particular class of feasible bases, we provide a complete characterisation, and we deduce a recursion formula for the number of feasible bases of a particular type within this class. Results on: We discuss that sampling extreme points of this polytope corresponds to sampling extreme points of the perfect matching polytope for an auxiliary graph associated with the input graph. Thus, the known results about sampling perfect matchings can be used for sampling extreme points of this polytope. Besides, we demonstrate that the number of Hamiltonian extreme points of this polytope is within a polynomial factor of the total number of extreme points when the input graph is a moderately dense random directed graph. Also, we show that the expected number of Hamiltonian bases is within a polynomial factor of the expected total number of feasible bases.
- Subject
- Hamilton cycles; combinatorics; polytopes; polynomial factors
- Identifier
- http://hdl.handle.net/1959.13/1438623
- Identifier
- uon:40668
- Rights
- Copyright 2020 Sogol Mohammadian
- Language
- eng
- Full Text
- Hits: 2374
- Visitors: 1063
- Downloads: 248
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Thesis | 14 MB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Abstract | 1 MB | Adobe Acrobat PDF | View Details Download |